package algorithms.evictpolicy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LRU<K, V> {
    private int size;
    private int tail;
    protected K[] queue;
    private Map<K, IndexAndValue> data;

    @SuppressWarnings("unchecked")
    public LRU(int size) {
        this.size = size;

        queue = (K[]) new Object[this.size];
        tail = 0;
        data = new HashMap<>();
    }

    protected class IndexAndValue {
        V value;
        int index;

        IndexAndValue(V value, int index) {
            this.value = value;
            this.index = index;
        }

        @Override
        public String toString() {
            return "[" +
                "index=" + index +
                ",value=" + value +
                ']';
        }
    }

    /**
     * CURD-R
     *
     * @param k
     * @return
     */
    public boolean exists(K k) {
        return data.containsKey(k);
    }

    public V get(K k) {
        IndexAndValue indexAndValue = data.get(k);
        if (indexAndValue == null) return null;
        swapToTail(indexAndValue);
        return indexAndValue.value;
    }

    private void swapToTail(IndexAndValue indexAndValue) {
        int index = indexAndValue.index;
        K k = queue[index];
        moveForward(index);
        queue[tail - 1] = k;
        indexAndValue.index = tail - 1;
    }

    private void moveForward(int index) {
        for (int i = index; i < tail - 1; i++) {
            K ki1 = queue[i + 1];
            IndexAndValue vi1 = data.get(ki1);
            vi1.index = i;
            queue[i] = ki1;
        }
    }


    /**
     * CURD-CU
     *
     * @param k
     * @param v
     */
    public void put(K k, V v) {
        IndexAndValue indexAndValue = data.get(k);
        if (indexAndValue != null) {
            swapToTail(indexAndValue);
            return;
        }

        if (tail == size) {
            shiftHead();
        } else {
            tail++;
        }
        int index = tail - 1;
        queue[index] = k;
        indexAndValue = new IndexAndValue(v, index);
        data.put(k, indexAndValue);
    }


    /**
     * CURD-D
     *
     * @param k
     */
    public void remove(K k) {
        IndexAndValue indexAndValue = data.get(k);
        if (indexAndValue == null) return;

        int index = indexAndValue.index;
        moveForward(index);
        data.remove(k);
        queue[--tail] = null;
    }


    private void shiftHead() {
        K k = queue[0];
        data.remove(k);
        int end = tail - 1;
        for (int i = 0; i < end; i++) {
            K ki1 = queue[i + 1];
            IndexAndValue vi1 = data.get(ki1);
            vi1.index = i;
            queue[i] = ki1;
        }
    }

    @Override
    public String toString() {
        return "LRU:{\n" +
            "\tsize = " + size +
            ",\n\ttail = " + tail +
            ",\n\tqueue = " + Arrays.toString(queue) +
            ",\n\tdata = " + data +
            "\n}";
    }

    public static void main(String[] args) {
        LRU<String, Integer> cache = new LRU<>(5);
        cache.put("Q", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        cache.put("D", 4);
        cache.put("E", 5);
        cache.put("F", 6);
        cache.put("C", 33);
        cache.remove("D");
        cache.get("B");
        cache.get("Q");

        System.out.println(cache);
    }
}
